/*
295. 数据流的中位数

思路: 大根堆存前一半较小的数，小根堆存后一半较大的数，存数据要平衡，先入大根堆，如果比大根堆peek要大，入小根堆。
两个堆之间size差不超过1
中位数为：  个数为偶数， 两个堆堆顶元素平均，  个数为奇数，哪个堆size大返回哪个。
 */
import Heap from './heap'

/**
 * initialize your data structure here.
 */
var MedianFinder = function () {
  this.maxHeap = new Heap((a, b) => a > b)
  this.minHeap = new Heap((a, b) => a < b)
}

/**
 * @param {number} num
 * @return {void}
 */
MedianFinder.prototype.addNum = function (num) {
  if (this.maxHeap.size() === 0) {
    this.maxHeap.push(num)
    return
  }
  if (num > this.maxHeap.peek()) {
    this.minHeap.push(num)
  } else {
    this.maxHeap.push(num)
  }
  // 平衡
  if (this.maxHeap.size() > this.minHeap.size() + 1) {
    const elem = this.maxHeap.pop()
    this.minHeap.push(elem)
  } else if (this.minHeap.size() > this.maxHeap.size() + 1) {
    const elem = this.minHeap.pop()
    this.maxHeap.push(elem)
  }
}

/**
 * @return {number}
 */
MedianFinder.prototype.findMedian = function () {
  const maxHeapSize = this.maxHeap.size()
  const minHeapSize = this.minHeap.size()
  if ((maxHeapSize + minHeapSize) % 2 === 1) {
    return maxHeapSize > minHeapSize ? this.maxHeap.peek() : this.minHeap.peek()
  }
  return (this.maxHeap.peek() + this.minHeap.peek()) / 2
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * var obj = new MedianFinder()
 * obj.addNum(num)
 * var param_2 = obj.findMedian()
 */
var obj = new MedianFinder()
obj.addNum(-1)
console.log(obj.findMedian())
obj.addNum(-2)
console.log(obj.findMedian())
obj.addNum(-3)
console.log(obj.findMedian())
obj.addNum(-4)
console.log(obj.findMedian())
obj.addNum(-5)
console.log(obj.findMedian())
/* var obj = new MedianFinder()
obj.addNum(1)
console.log(obj.findMedian())
obj.addNum(2)
console.log(obj.findMedian())
obj.addNum(3)
console.log(obj.findMedian()) */
